A. Field of the Invention
This invention relates generally to a method and an apparatus for culling and, more particularly, to a method and an apparatus for accelerating culling tests in computer graphics systems.
B. Description of the Related Art
A computer graphics system is commonly used to display three-dimensional representations of an object on a two-dimensional display screen. In a typical computer graphics system, an object to be rendered is divided into a plurality of graphics primitives. The graphics primitives are basic components of a graphics picture and may be defined by geometries of a point, line, vector, or polygon, such as a triangle. The graphics primitives are fed through a graphics pipeline where various types of processing occur and are then rendered on a display.
Culling, also called backface elimination, is an operation that compares the orientation of polygons in a polyhedron with the viewpoint or center of projection, and removes those polygons that cannot be seen. On average, half of the polygons in a polyhedron are backfacing and the advantage of this process is by using a simple test to remove these polygons. The test for visibility is straightforward and is best carried out in view space. We calculate the outward normal of a polygon and examine the sign of the dot product of this normal vector and the vector from the center of projection, as illustrated in FIG. 1.
As shown in FIG. 1 are the outward normal vector of a polygon Np, and the xe2x80x98line of sightxe2x80x99 vector N from the center of the face to the viewpoint. Based on these two vectors, the visibility of a polygon is defined as:
xe2x80x83Visibility=Npxc2x7N greater than 0
Where:
Np is the polygon normal
N is the xe2x80x98line of sightxe2x80x99 vector
In order to determine whether a polygon is visible on a two-dimensional flat screen, select three points V1, V2, and V3 from the polygon where the V1 is the center point, V2 and V3 are any points on the surface which satisfy the condition that V1, V2, and V3 are not on the same line, and (V1, V2, V3) is distributed counterclockwise.
From the visibility test:
Visibility=Npxc2x7N[(V2xe2x88x92V1)xc3x97(V3xe2x88x92V1)]xc2x7(V1xe2x88x92V0) greater than 0
Where:
V0 is the viewpoint (0, 0, 0), and
V1, V2, and V3 are the selected vertices (x1, y1, z1), (x2, y2, z2), and (x3, y3, z3) for a triangle.
The calculation for the visibility test is:   Visibility  =      |                                        x            1                                                y            1                                                z            1                                                            x            2                                                y            2                                                z            2                                                            x            3                                                y            3                                                z            3                                |           greater than       0      
Although the equation for the culling test may seem to be relatively simple and straightforward, it takes twelve multiplication processes and five addition/subtraction processes to complete the whole calculation to test the visibility for one triangle. For two triangles, hence, it takes 24 multiplications and 10 addition/subtractions. Not only is the calculation process unwieldy but also time-consuming.
In view of these problems, the object of the present invention is to provide a method and an apparatus for use in computer graphics system which can render and display graphics primitives faster.
In one aspect of the present invention, a method is provided for determining, at the same time, whether two adjacent polygons of a polyhedron are visible on a 2-dimensional visual display unit. The test can be done more easily and rapidly. It lends itself to rapid real-time culling and eliminates surfaces certain to be not visible at the observer""s viewpoint.
Another aspect of the present invention is to provide an apparatus to execute the culling test described above. The culling apparatus comprises one multiplier, three multiplexers, two registers, one adder/subtractor, and a computer program with a set of commands controlling the flow and process of data. The instruction commands may be installed in ROM to be used in the computer graphic systems in order to compute and control all data inputs and outputs of culling test.
The benefits of this invention will become evident as the present invention is described more fully below.